As pervasive computing technologies develop fast, the privacy protection becomes a crucial issue and needs to be coped with very carefully. Typically, it is difficult to efficiently identify and manage plenty of the low-cost pervasive devices like Radio Frequency Identification Devices (RFID), without leaking any privacy information. In particular, the attacker may not only eavesdrop the communication in a passive way, but also mount an active attack to ask queries adaptively, which is obviously more dangerous. Towards settling this problem, in this paper, we propose two lightweight authentication protocols which are privacy-preserving against active attack, in an asymmetric way. That asymmetric style with privacy-oriented simplification succeeds to reduce the load of low-cost devices and drastically decrease the computation cost for the management of server. This is because that, unlike the usual management of the identities, our approach does not require any synchronization nor exhaustive search in the database, which enjoys great convenience in case of a large-scale system. The protocols are based on a fast asymmetric encryption with specialized simplification and only one cryptographic hash function, which consequently assigns an easy work to pervasive devices. Besides, our results do not require the strong assumption of the random oracle.

Illegal distribution of signed documents can be considered as one of serious problems of digital signatures. In this paper, to solve the problem, we propose three protocols concerning signature schemes. These schemes achieve not only traceability of an illegal user but also universal verifiability. The first scheme is a basic scheme which can trace an illegal receiver, and the generation and tracing of a signed document are simple and efficient. However, in this scheme, it is assumed that a signer is honest. The second scheme gives another tracing method which does not always assume that a signer is honest. Furthermore, in the method, an illegal user can be traced by an authority itself, hence, it is efficient in terms of communication costs. However, in this scheme it is assumed that there exists only a legal verification algorithm. Thus, in general, this scheme cannot trace a modified signed document which is accepted by a modified verification algorithm. The third one is a scheme which requires no trusted signer and allows a modified verification algorithm. It can trace an illegal receiver or even a signer in such a situation. All of our schemes are constructed by simple combinations of standard signature schemes, consequently, one can flexibly choose suitable building blocks for satisfying requirements for a system.

We propose a scheme for the design of irregular low-density parity-check (LDPC) codes based on Euclidian Geometry using Latin square matrices of random sequence. Our scheme is a deterministic method that allows the easy design of good irregular LDPC codes for any code rate and degree distribution. We optimize the LDPC codes using the Gaussian approximation method. A Euclidean Geometry LDPC code (EG-LDPC) is used as the basis for the construction of an irregular LDPC code. The base EG-LDPC code is extended by splitting rows and columns using a table of Latin square matrices of random sequence to determine the edges along which to split. We provide simulation results for codes constructed in this manner evaluated in terms of bit error rate (BER) performance in AWGN channels. We believe that our scheme is superior in terms of computational requirements and resulting BER performance in comparison to creation of irregular LDPC codes by means of random construction using a search algorithm to exclude cycles of length four.

Computer systems are constantly under attack and illegal access is a constant threat which makes security even more critical. A system can be broken into and secret information, e.g. decryption key, may be exposed, resulting in a total break of the system. Recently, a new framework for the protection against such key exposure problem was suggested and was called, Key-Insulated Encryption (KIE). In our paper, we introduce a novel approach to key insulated cryptosystems that offers provable security without computational assumptions. For the model of Information-Theoretically Secure Key-Insulated Encryption (ISKIE), we show lower bounds on required memory sizes of user, trusted device and sender. Our bounds are all tight as our concrete construction of ISKIE achieves all the bounds. We also extend this concept further by adding an extra property so that any pair of users in the system is able to communicate with each other and still have the same security benefits as the existing KIE based on intractability assumptions. We called this, Dynamic and Mutual Key-Insulated Encryption (DMKIE), and concrete implementations of DMKIE will be shown as well. In the end, we discuss the relationship of DMKIE against Key Predistribution Schemes (KPS) and Broadcast Encryption Schemes (BES), that is, we show that DMKIE can be constructed from either KPS or BES.

In many cryptosystems incorporating human beings, the users' limited memories and their indifference to keeping the systems secure may cause some severe vulnerability of the whole systems. Thus we need more studies on personal entropy, from an information theoretical point of view, to capture the characteristics of human beings as special information sources for cryptosystems. In this paper, we discuss and analyze the use of personal entropy for generating cryptographic keys. In such a case, it is crucially important to precisely evaluate the amount of personal entropy that indicates the actual key length. We propose an advanced key generation scheme based on the conventional graphical passwords proposed in [12]. We improve them to make the most of the secret information extracted in one drawing, i.e., we incorporate the on-line pen pressure and pen inclination information in addition to utilize more secret information. We call the scheme dynamic graphical passwords, and propose a practical construction of them. We also show a precise way of quantifying their entropy, and finally, as an experimental result, we can generate a key of over 110-bit long, using the data of a single drawing. When quantifying their entropy, we need to precisely evaluate the entropy of graphical passwords as well as that of the on-line information of pen movements. We need to precisely evaluate the entropy of graphical passwords by considering the users' biased choices of their graphical passwords. It is expected that they tend to choose their passwords that are memorable as easily as possible, thus we quantify the burden of memorizing each graphical password by the length of its description using a special language based on [12]. We improve the approach in [12] by more directly reflecting how easily each graphical password can be memorized.

In this paper we propose a two-stage address coding scheme to transmit two data symbols at once within a frame in a MFSK/FH-CDMA system. We compare it with the conventional system using single-stage address coding. Assumed that the address codes of all users are known in the receiver. A multiuser detection scheme is applied and the performance is evaluated by computer simulations to show the improvement in bit error rate (BER) compairing to the conventional system. We also investigate the performance of error-correcting coding and decoding in the two-stage address coded MFSK/FH-CDMA system. An erasure decoding scheme is modified for the two-stage address coded system and is utilized to improve spectral efficiency or to increase user capacity in the MFSK/FH-CDMA system. Finally, we investigate a hybrid scheme of combining the multi-user detection scheme and the error-correcting decoding scheme for the two-stage address coded MFSK/FH-CDMA system. The performance is evaluated by computer simulations.

The WEP (Wired Equivalent Privacy) is a part of IEEE 802.11 standard designed for protecting over the air communication. While almost all of the WLAN (Wireless LAN) cards and the APs (Access Points) support WEP, a serious key recovery attack (aka FMS attack) was identified by Fluhrer et al. The attack was then extended and implemented as WEP cracking tools. The key recovery attacks can basically be prevented by skipping certain IVs (Initial Values) called weak IVs, but the problem is that there exist huge amount of key-dependent weak IVs and the patterns of them have not been fully identified yet. The difficult part is that a naive approach to identify the key-dependent weak IVs requires the exhaustive search of IVs and WEP keys, and hence is infeasible. On the other hand, it might be feasible to skip the key-dependent weak IVs for the currently set WEP key but this reveals information on the WEP key from the skipped patterns. To skip them safely, the patterns of the key-dependent weak IVs must be identified in the first place. In this paper, we analyze the famous condition for IVs and WEP keys to be weak in the FMS attack, i.e. 0≤S[1]≤t'

This paper investigates a multihopping scheme for MFSK (Multilevel Frequency Shift Keying) /FH-SSMA (Frequency Hopping-Spread Spectrum Multiple Access) system. Moreover, we propose and investigate a modified decoding scheme for the coded MFSK/FH-SSMA system. In this multi-hopped MFSK/FH-SSMA system, several hopping frequencies per chip are assigned and transmitted in parallel in order to improve its frequency diversity capability for a fading channel. We theoretically analyze the performance of the multihopped MFSK/FH-SSMA system in a Rayleigh fading channel. Moreover, in the coded MFSK/FH-SSMA system, we propose a modified scheme of the error and erasure decoding of an error-correcting code. The modified decoding scheme utilizes the information of rows having the largest number of entries in the decoded time-frequency matrix. Their BER (Bit Error Rate) performance is evaluated by theoretical analysis in order to show the improvement in user capacity.

Recently, a lot of research works have been carried out regarding intelligent communication. If the final information sink is assumed as a human being, a communication channel can be used more effectively when encoders/decoders work "intelligently" or take into account of the semantics of information to be sent. We have been studying error-controlling systems based on different importance of segmental information. The system divides the information input into segments to which individual importance can be assigned. The segments are individually encoded by appropriate error-correcting codes (ECCs) which correspond to their importance among codes with different error-correcting capabilities. For the information that difference of the importance is systematically aligned, conventional UEP (unequal error protection) codes can be applied, but we treat the case that alignment of the importance of the information source is not systematically aligned. Since the system uses multiple ECCs with different (n,k,d) parameters, information regarding what length of the next codeword is required for decoding. We propose error controlling schemes using mulriple ECCs; the first scheme and the second scheme use the obvious codelength identifying information. In the second scheme, information bits are sorted so that segments with the same importance can be encoded by an ECC with the same error-correcting capability. The third scheme is a main proposal in this paper and uses Variable Capability Coding scheme (VCC) which uses some ECCs having different error-correcting capabilities and codelengths. A sequence encoded by the VCC is separable into appropriate segments without obvious codelength identifying information when the channel error probability is low. Subsequently, we evaluate these schemes by coderate when (1) error correcting capability (2) codelength identifying capability are the same. One of the feature of VCC is the capability of resuming from propagative errors because errors beyond the codelength identifying capability occur and the proper beginning of the codeword is lost in the decoder. We also evaluate this capability as (3) resynchronizing capability.

Recently a framework called Tag-KEM/DEM was introduced to construct efficient hybrid encryption schemes. Although it is known that generic encode-then-encrypt construction of chosen ciphertext secure public-key encryption also applies to secure Tag-KEM construction and some known encoding method like OAEP can be used for this purpose, it is worth pursuing more efficient encoding method dedicated for Tag-KEM construction. This paper proposes an encoding method that yields efficient Tag-KEM schemes when combined with set partial one-way permutations such as RSA and Rabin's encryption scheme. To our knowledge, this leads to the most practical hybrid encryption scheme of this type. We also present an efficient Tag-KEM which is CCA-secure under general factoring assumption rather than Blum factoring assumption.

The problem we consider in this paper is whether the Menezes-Okamoto-Vanstone (MOV) reduction for attacking elliptic curve cryptosystems can be realized for genera elliptic curves. In realizing the MOV reduction, the base field Fq is extended so that the reduction to the discrete logarithm problem in a finite field is possible. Recent results by Balasubramanian and Koblitz suggest that, if l q-1, such a minimum extension degree is the minimum k such that l|qk-1, which is equivalent to the condition under which the Frey-Ruck (FR) reduction can be applied, where l is the order of the group in the elliptic curve discrete logarithm problem. Our point is that the problem of finding an l-torsion point required in evaluating the Weil pairing should be considered as well from an algorithmic point of view. In this paper, we actually propose a method which leads to a solution of the problem. In addition, our contribution allows us to draw the conclusion that the MOV reduction is indeed as powerful as the FR reduction under l q-1 not only from the viewpoint of the minimum extension degrees but also from that of the effectiveness of algorithms.

The security of biometric authentication systems against impersonation attack is usually evaluated by the false accept rate, FAR. The false accept rate FAR is a metric for zero-effort impersonation attack assuming that the attacker attempts to impersonate a user by presenting his own biometric sample to the system. However, when the attacker has some information about algorithms in the biometric authentication system, he might be able to find a “strange” sample (called a wolf) which shows high similarity to many templates and attempt to impersonate a user by presenting a wolf. Une, Otsuka, Imai [22],[23] formulated such a stronger impersonation attack (called it wolf attack), defined a new security metric (called wolf attack probability, WAP), and showed that WAP is extremely higher than FAR in a fingerprint-minutiae matching algorithm proposed by Ratha et al. [19] and in a finger-vein-patterns matching algorithm proposed by Miura et al. [15]. Previously, we constructed secure matching algorithms based on a feature-dependent threshold approach [8] and showed that if the score distribution is perfectly estimated for each input feature data, then the proposed algorithms can lower WAP to a small value almost the same as FAR. In this paper, in addition to reintroducing the results of our previous work [8], we show that the proposed matching algorithm can keep the false reject rate (FRR) low enough without degrading security, if the score distribution is normal for each feature data.

The code length of Tardos's collusion-secure fingerprint code is of theoretically minimal order with respect to the number of adversarial users (pirates). However, the constant factor should be further reduced for practical implementation. In this article, we improve the tracing algorithm of Tardos's code and propose a 2-secure and short random fingerprint code, which is secure against collusion attacks by two pirates. Our code length is significantly shorter than that of Tardos's code and its tracing error probability is practically small.

So far, in almost all of the practical public key encryption schemes, hash functions which are dependent on underlying cyclic groups are necessary, e.g., H:{0,1}* → Zp where p is the order of the underlying cyclic group, and it could be required to construct a dedicated hash function for each public key. The motivation of this note is derived from the following two facts: 1). there is an important technical gap between hashing to a specific prime-order group and hashing to a certain length bit sequence, and this could cause a security hole; 2). surprisingly, to our best knowledge, there is no explicit induction that one could use the simple construction, instead of tailor-made hash functions. In this note, we investigate this issue and provide the first rigorous discussion that in many existing schemes, it is possible to replace such hash functions with a target collision resistant hash function H:{0,1}* → {0,1}k, where k is the security parameter. We think that it is very useful and could drastically save the cost for the hash function implementation in many practical cryptographic schemes.

An algorithm for cryptanalysis of certain keystream generators is proposed. The developed algorithm has the following two advantages over other reported ones: it is more powerful, and it can be implemented by a high-speed software or a simple hardware suitable for high parallel architectures. The algorithm is based on error-correction of information bits only (of the corresponding binary block code) with a novel method for construction of the parity-checks, and the employed error-correction procedure is an APP based threshold decoding. Experimental and theoretical analyses of the algorithm performance are presented, and its complexity is evaluated. The proposed algorithm is compared with recently proposed improved fast correlation attacks based on convolutional codes and turbo decoding. The underlying principles, performance and complexity are compared, and the gain obtained with the novel approach is pointed out.

Internet Key Exchange (IKE) is very important as an entrance to secure communication over the Internet. The first phase of IKE is based on Diffie-Hellman (DH) key-agreement protocol. Since DH protocol on its own is vulnerable to man-in-the-middle (MIM) attack, IKE provides authentication to protect the protocol from MIM. This authentication owes a lot to public-key primitives whose implementation includes modular exponentiation. Since modular exponentiation is computationally expensive, attackers are motivated to abuse it for Denial-of-Service (DoS) attacks; computational burden caused by malicious requests may exhaust the CPU resource of the target. DoS attackers can also abuse inappropriate use of Cookies in IKE; as an anti-clogging token, Cookie must eliminate the responder's state during initial exchanges of the protocol while IKE Cookies do not. Thus a large number of malicious requests may exhaust the memory resource of the target. In search of resistance against those DoS attacks, this paper first reviews DoS-resistance of the current version of IKE and basic ideas on DoS-protection. The paper then proposes a DoS-resistant version of three-pass IKE Phase 1 where attackers are discouraged by heavy stateful computation they must do before the attack really burdens the target. DoS-resistance is evaluated in terms of the computational cost and the memory cost caused by bogus requests. The result shows that the proposed version gives the largest ratio of the attacker's cost to the responder's cost.

A function can be represented in many ways. A representation O of a function f is called 'obscure' if O is different from the representation D used as the definition of f and if it is (or, seems to be) computationally infeasible to get D from O. Such an obscure representation is useful for cryptographic techniques so that it is important to estimate its descriptive and executive complexity. We present a complexity-estimation method for certain functions used to constructing asymmetric cryptosystems. Let m be a positive integer and let K, Km, and L denote the field {0, 1}, the set of all m-tuples over K, and an extention field or order m over K, respectively. The objective function is a composit g:Km Km of three functions s, e, and t, where s:Km L and t:L Km are affine and e:L L is defined by a univariate polynomial e over L. The obscure representation of g is an m-tuple g of m-variate polynomials over K. The complexity respect to g is well measured by its degree. So we give a theorem for estimating the degree of g in terms of a characteristic quantity of the polynomial e.

To utilize the common-key encryption foe the message protection in a communication network, it is desired to settle the problem of how to distribute the common keys. This paper discusses a sort of schemes (the direct schemes, we call) that smartly provide different keys in different communications. Such a property has not attained via the basic scheme for the public key distribution systems proposed by Diffie and Hellman. This paper shows that the recently introduced five direct schemes are classified into three sets (called sequences) of infinite schemes, and points out that there are some tight relations among the sequences. And it is clarified which is the best in the three sequences by a systematic evaluation of the complexities for the normal update and for the deliberate forgery of the shared common keys.

Let γ and n be positive integers. An integer z with gcd(z, n)1 is called a γth-residue mod n if there exists an integer x such that zxγ (mode n), or a γth-nonresidue mod n if there doesn't exist such an x. Denote by Z*n the set of integers relatively prime to n between 0 and n. The problem of determining whether or not a randomly selected element zZ*n is a γth-residue mod n is called the γth-Residuosity Problem (γth-RP), and appears to be intractable when n is a composite integer whose factorization is unknown. In this paper, we explore some important properties of γth-RP for the case where γ is an odd integer greater than 2, and discuss its applications to cryptography. Based on the difficulty or γth-RP, we generalize the Goldwasser-Micali bit-by-bit probabilistic encryption to a block-by-block probabilistic one, and propose a direct protocol for the dice casting problem over a network. This problem is a general one which includes the well-studied coin flipping problem.

Unforgeability of digital signatures is closely related to the security of hash functions since hashing messages, such as hash-and-sign paradigm, is necessary in order to sign (arbitrarily) long messages. Recent successful collision finding attacks against practical hash functions would indicate that constructing practical collision resistant hash functions is difficult to achieve. Thus, it is worth considering to relax the requirement of collision resistance for hash functions that is used to hash messages in signature schemes. Currently, the most efficient strongly unforgeable signature scheme in the standard model which is based on the CDH assumption (in bilinear groups) is the Boneh-Shen-Waters (BSW) signature proposed in 2006. In their scheme, however, a collision resistant hash function is necessary to prove its security. In this paper, we construct a signature scheme which has the same properties as the BSW scheme but does not rely on collision resistant hash functions. Instead, we use a target collision resistant hash function, which is a strictly weaker primitive than a collision resistant hash function. Our scheme is, in terms of the signature size and the computational cost, as efficient as the BSW scheme.